#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int subarraysDivByK(const vector<int>& nums, int k) {
    int n = nums.size();
    int ret = 0;
    int sum = 0;
    unordered_map<int, int> hash;
    hash[0] = 1;

    for (auto e : nums)
    {
        sum += e;
        int r = (sum % k + k) % k;
        if (hash.count(r))   
            ret += hash[r];
        hash[r]++;
    }

    return ret;
}

int main()
{
    subarraysDivByK({ 4, 5, 0, -2, -3, 1 }, 5);
	return 0;
}